home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / gnu / nihcl-30.lha / nihcl-3.0 / lib / Heap.c < prev    next >
C/C++ Source or Header  |  1990-05-19  |  11KB  |  519 lines
  1. /* Heap.c  -- implementation of abstract Heap class
  2.  
  3.     THIS SOFTWARE FITS THE DESCRIPTION IN THE U.S. COPYRIGHT ACT OF A
  4.     "UNITED STATES GOVERNMENT WORK".  IT WAS WRITTEN AS A PART OF THE
  5.     AUTHOR'S OFFICIAL DUTIES AS A GOVERNMENT EMPLOYEE.  THIS MEANS IT
  6.     CANNOT BE COPYRIGHTED.  THIS SOFTWARE IS FREELY AVAILABLE TO THE
  7.     PUBLIC FOR USE WITHOUT A COPYRIGHT NOTICE, AND THERE ARE NO
  8.     RESTRICTIONS ON ITS USE, NOW OR SUBSEQUENTLY.
  9.  
  10. Author:
  11.     C. J. Eppich
  12.     Bg. 12A, Rm. 2025
  13.     Computer Systems Laboratory
  14.     Division of Computer Research and Technology
  15.     National Institutes of Health
  16.     Bethesda, Maryland 20892
  17.     Phone: (301) 496-5361
  18.     March, 1987
  19.  
  20. Function:  The Min-Max Heap is implemented as described by Atkinson,
  21. Sack, Santoro, and Strothotte (1986).  Objects may be added; the min
  22. or max may be accessed with first() or last(), respectively, or removed
  23. with removeFirst() or removeLast(), respectively.
  24.     
  25. $Log:    Heap.c,v $
  26.  * Revision 3.0  90/05/20  00:19:42  kgorlen
  27.  * Release for 1st edition.
  28.  * 
  29. */
  30.  
  31. #include <libc.h>
  32. #include "Heap.h"
  33. #include "nihclIO.h"
  34.  
  35. #define    THIS    Heap
  36. #define    BASE    SeqCltn
  37. #define BASE_CLASSES BASE::desc()
  38. #define MEMBER_CLASSES ArrayOb::desc()
  39. #define VIRTUAL_BASE_CLASSES
  40.  
  41. DEFINE_CLASS(Heap,1,"$Header: /afs/alw.nih.gov/unix/sun4_40c/usr/local/src/nihcl-3.0/share/lib/RCS/Heap.c,v 3.0 90/05/20 00:19:42 kgorlen Rel $",NULL,NULL);
  42.  
  43. extern const int NIHCL_CLTNEMPTY;
  44.  
  45. static int heap_capacity;
  46.  
  47.  
  48. // CONSTRUCTORS:
  49.  
  50. Heap::Heap(int size) : contents(size)
  51. {
  52.     endIndex = 0;
  53. }
  54.  
  55. Heap::Heap(const ArrayOb &a) : contents(a)
  56. {
  57.     endIndex = a.size();
  58.     for (int i = endIndex - 2; i >= 0; i--)
  59.         trickleDown(i);
  60. }
  61.  
  62. #ifndef BUG_TOOBIG
  63. // yacc stack overflow
  64. Heap::Heap(const Heap& c) : contents(c.contents)
  65. {
  66.     endIndex = c.endIndex;
  67. }
  68. #endif
  69.  
  70. Heap::Heap(OIOin& strm)
  71. :
  72. #ifdef MI
  73.     Object(strm),
  74. #endif
  75.     BASE(strm),
  76.     contents((strm >> heap_capacity, heap_capacity))
  77. {
  78.     endIndex = 0;
  79.     int n;
  80.     strm >> n;        // read collection size 
  81.     while (n--)
  82.          add(*Object::readFrom(strm));
  83. }
  84.  
  85. Heap::Heap(OIOifd& fd)
  86. :
  87. #ifdef MI
  88.     Object(fd),
  89. #endif
  90.     BASE(fd),
  91.     contents((fd >> heap_capacity, heap_capacity))
  92. {
  93.     endIndex = 0;
  94.     int n;
  95.     fd >> n;
  96.     while (n--) add(*Object::readFrom(fd));
  97. }
  98.  
  99. void Heap::storer(OIOofd& fd) const
  100. {
  101.     BASE::storer(fd);
  102.     _storer(fd);
  103. }
  104.  
  105. void Heap::storer(OIOout& strm) const
  106. {
  107.     BASE::storer(strm);
  108.     _storer(strm);
  109. }
  110.  
  111. // OPERATORS:
  112.  
  113. void Heap::operator=(const Heap& a)
  114. {
  115.     endIndex = a.endIndex;
  116.     contents = a.contents;
  117. }
  118.  
  119. bool Heap::operator==(const Heap& a) const
  120. {
  121.     if (endIndex != a.endIndex) 
  122.         return NO;
  123.     else 
  124.     {
  125.         Heap heap1 = *this;
  126.         Heap heap2 = a;
  127.         while (heap1.endIndex)
  128.              if (!(heap1.removeFirst()->isEqual(*heap2.removeFirst())))
  129.                 return NO;
  130.     }
  131.     return YES;
  132. }
  133.  
  134. // NonPublic MEMBER FUNCTIONS
  135.  
  136. void Heap:: bubbleUp(int i)
  137. //Atkinson,et.al.(1986) -- determine correct position of last element of heap.
  138. {
  139.     int father;    
  140.     if ((level(i) & 1) == 0)     // i is on min level
  141.  
  142.         if ( (i > 0)    // then i has a parent
  143.          && (contents[i]->compare(*contents[father=parent(i)])>0))
  144.         {
  145.             swap(i,father);
  146.             bubbleUpMax(father);
  147.         }
  148.         else bubbleUpMin(i);
  149.     
  150.     else    // i is on max level
  151.  
  152.         if ( (i > 0)
  153.           && (contents[i]->compare(*contents[father=parent(i)])<0))
  154.         {
  155.             swap(father,i);
  156.             bubbleUpMin(father);
  157.         }
  158.         else bubbleUpMax(i);
  159. }
  160.  
  161. void Heap::bubbleUpMax(int i)
  162. {
  163.     int grandparent;
  164.     if ( (i > 6)    //then i has a grandparent
  165.           && (contents[i]->compare
  166.           (*contents[grandparent=parent(parent(i))]) > 0))
  167.     {
  168.         swap(i,grandparent);
  169.         bubbleUpMax(grandparent);
  170.     }
  171. }
  172.  
  173. void Heap::bubbleUpMin(int i)
  174. {
  175.     int grandparent;
  176.     if ( (i > 2)    //then i has a grandparent
  177.           && (contents[i]->compare
  178.           (*contents[grandparent=parent(parent(i))]) < 0))
  179.     {
  180.         swap(i,grandparent);
  181.         bubbleUpMin(grandparent);
  182.     }
  183. }
  184.  
  185.  
  186. int Heap::descendents(int i) const
  187. // Returns number of children and grandchildren of heap element with index i.
  188. {
  189.     if (endIndex <= child(i))     return(0);
  190.     else if (endIndex <= grandchild(i))    // No grandchildren
  191.         return MIN(2,(endIndex - child(i)));
  192.     else return MIN(6,(2 + endIndex - grandchild(i)));
  193. }
  194.  
  195. void Heap::errEmpty(const char* fn) const
  196. {
  197.     setError(NIHCL_CLTNEMPTY,DEFAULT,this,className(),fn);
  198. }
  199.  
  200. int Heap::largest(int a, int i) const
  201. // Return Heap index with largest value from children and grandchildren
  202. // of i. a is number of children and grandchildren & must be > 0.
  203. {
  204.     int maxIndex = child(i);
  205.     Object* max = (Object*)contents[maxIndex];
  206.     if (a > 1)
  207.         {    if (contents[child(i)+1]->compare(*max) > 0)
  208.             max = (Object*)contents[++maxIndex];
  209.         if (a > 2)
  210.         {
  211.             Object** grandcPtr = (Object**)&contents[grandchild(i)];
  212.             for (int k=0; k < (a - 2); k++)
  213.             {
  214.                 if ((*grandcPtr)->compare(*max) > 0)
  215.                 {
  216.                     maxIndex = grandchild(i) + k;
  217.                     max = *grandcPtr;
  218.                 }
  219.                 grandcPtr++;
  220.             }
  221.         }
  222.     }
  223.     return(maxIndex);
  224. }
  225.  
  226. int Heap::level(int i)
  227. //returns level that ith element is on
  228. {
  229.     int l = 0;
  230.     for (int index = i+1; index > 1; index >>=1)  l++;
  231.     return(l);
  232. }
  233.  
  234. Object* Heap::removeAtIndex(int i)
  235. {
  236.     register Object* obrem = contents[i];
  237.     contents[i] = contents[--endIndex];
  238.     bubbleUp(i);
  239.     trickleDown(i);
  240.     return obrem;
  241. }
  242.  
  243. int Heap::smallest(int a, int i) const
  244. // Return Heap index with smallest value from children and grandchildren
  245. // of i. a is number of children and grandchildren & must be > 0.
  246. {
  247.     int minIndex = child(i);
  248.     Object* min = (Object*)contents[minIndex];
  249.     if (a > 1) 
  250.     {    if (contents[child(i)+1]->compare(*min) < 0)
  251.             min = (Object*)contents[++minIndex];
  252.         if (a > 2)
  253.         {
  254.             Object** grandcPtr = (Object**)&contents[grandchild(i)];
  255.             for (int k=0; k < (a - 2); k++)
  256.             {
  257.                 if ((*grandcPtr)->compare(*min) < 0)
  258.                 {
  259.                     minIndex = grandchild(i) + k;
  260.                     min = *grandcPtr;
  261.                 }
  262.                 grandcPtr++;
  263.             }
  264.         }
  265.     }
  266.     return(minIndex);
  267. }
  268.  
  269. void Heap::trickleDown(int i)
  270. {
  271.     if ((level(i) & 1) == 0)     // i is on min level
  272.         trickleDownMin(i);
  273.     else    trickleDownMax(i);
  274. }
  275.  
  276. void Heap::trickleDownMax(int i)
  277. {
  278.     if (descendents(i))
  279.     {    int max = largest(descendents(i),i);
  280.         if (max >= grandchild(i))
  281.         {   if (contents[max]->compare(*contents[i]) > 0)
  282.             {
  283.             swap(i,max);
  284.             if (contents[max]->compare(*contents[parent(max)]) < 0)
  285.                 swap(max,parent(max));
  286.             trickleDownMax(max);
  287.             }
  288.         }
  289.         else  // max is child of i
  290.             if (contents[max]->compare(*contents[i]) > 0)
  291.             swap(i,max);
  292.     }
  293. }
  294.  
  295. void Heap::trickleDownMin(int i)
  296. {
  297.     if (descendents(i))
  298.     {
  299.         int min = smallest(descendents(i),i);
  300.         if (min >= grandchild(i))
  301.         {   if (contents[min]->compare(*contents[i]) < 0)
  302.             {
  303.             swap(i,min);
  304.             if (contents[min]->compare(*contents[parent(min)]) > 0)
  305.                 swap(min,parent(min));
  306.             trickleDownMin(min);
  307.             }
  308.         }
  309.         else  // min is child of i
  310.             if (contents[min]->compare(*contents[i]) < 0)
  311.             swap(i,min);
  312.     }
  313. }
  314.  
  315.  
  316. // PUBLIC MEMBER FUNCTIONS:
  317.  
  318. Object* Heap::add(Object& ob)
  319. {
  320.     if (endIndex == capacity())
  321.         contents.reSize(capacity() + EXPANSION_INCREMENT);
  322.     contents[endIndex++] = &ob;
  323.     bubbleUp(endIndex-1);
  324.     return this;
  325. }
  326.  
  327. Heap Collection::asHeap() const    // declaration in Collection.h
  328. {
  329.     Heap cltn(asArrayOb());
  330.     return cltn;
  331. }
  332.  
  333. Object*& Heap::at(int index)
  334. {
  335.     return contents.at(index);
  336. }
  337.  
  338. const Object *const& Heap::at(int index) const
  339. {
  340.     return contents.at(index);
  341. }
  342.  
  343. void Heap::atAllPut(Object&) { shouldNotImplement("atAllPut"); }
  344.  
  345. unsigned Heap::capacity() const    { return contents.capacity(); }
  346.  
  347. void Heap::deepenShallowCopy()
  348. {
  349.     BASE::deepenShallowCopy();
  350.     register int i = endIndex;
  351.     register Object** vv = &contents.elem(0);
  352.     while (i--) {
  353.         *vv = (*vv)->deepCopy();
  354.         vv++;
  355.     }
  356. }
  357.  
  358. void Heap::doReset(Iterator& pos) const
  359. {
  360.     BASE::doReset(pos);
  361.     if (pos.state != nil) {
  362.         Heap* hp = castdown(pos.state);
  363.         delete hp;
  364.     }
  365.     pos.state = new Heap(*this);
  366. }
  367.  
  368. Object* Heap::doNext(Iterator& pos) const
  369. {
  370.     Heap& h = *castdown(pos.state);
  371.     if (h.isEmpty()) return 0;
  372.     pos.index++;
  373.     return h.removeFirst();
  374. }
  375.  
  376. void Heap::doFinish(Iterator& pos) const
  377. {
  378.     if (pos.state != nil) {
  379.         Heap* hp = castdown(pos.state);
  380.         delete hp;
  381.     }
  382.     BASE::doFinish(pos);
  383. }
  384.  
  385. Object* Heap::first() const    // returns minimum object 
  386. {
  387.     if (endIndex==0) errEmpty("first");
  388.     else return (Object*)contents.elem(0);
  389. }
  390.  
  391. unsigned Heap::hash() const
  392. {
  393.     register unsigned h = endIndex;
  394.     register int i = endIndex;
  395.     register const Object** vv = &contents.elem(0);
  396.     while (i--) h^=(*vv++)->hash();
  397.     return h;
  398. }
  399.  
  400.  
  401. int Heap::indexOf(const Object&) const
  402. {
  403.     shouldNotImplement("indexOf");
  404.     return(0);
  405. }
  406.  
  407. int Heap::indexOfSubCollection(const SeqCltn&, int) const
  408. {
  409.      shouldNotImplement("indexOfSubCollection");
  410.     return(0);
  411. }
  412.  
  413. bool Heap::isEmpty() const    { return endIndex==0; }
  414.  
  415. Object* Heap::last() const    // returns maximum object
  416. {
  417.     if (endIndex==0)  errEmpty("last");
  418.     else if (endIndex==1) return (Object*)contents[0];
  419.     else if (endIndex==2) return (Object*)contents[1];
  420.     else if (contents[1]->compare(*contents[2]) > 0)
  421.         return (Object*)contents[1];
  422.         else return (Object*)contents[2];
  423. }
  424.  
  425. unsigned Heap::occurrencesOf(const Object& ob) const
  426. {
  427.     register unsigned n=0;
  428.     for (register int i=0; i<endIndex; i++)
  429.         if (contents[i]->isEqual(ob)) n++;
  430.     return n;
  431. }
  432.  
  433. Object* Heap::remove(const Object& ob)
  434. {
  435.     for (register int i=0; i<endIndex; i++) {
  436.         if (contents[i]->isEqual(ob)) {
  437.             return removeAtIndex(i);
  438.         }
  439.     }
  440.     return nil;
  441. }
  442.  
  443. Object* Heap::removeId(const Object& ob)
  444. {
  445.     for (register int i=0; i<endIndex; i++) {
  446.         if (contents[i]->isSame(ob)) {
  447.             return removeAtIndex(i);
  448.         }
  449.     }
  450.     return nil;
  451. }
  452.  
  453. void Heap::removeAll()
  454. {
  455.     contents.removeAll();
  456.     endIndex = 0;
  457. }
  458.  
  459. Object* Heap::removeFirst()     // remove the minimum element of the Heap
  460. {
  461.     Object* min = first();
  462.     contents[0] = contents[--endIndex];
  463.     trickleDownMin(0);
  464.     return(min);
  465. }
  466.  
  467. Object* Heap::removeLast()    // remove the maximum element of the Heap
  468. {
  469.     if (endIndex == 0)  errEmpty("removeLast");
  470.     else if (endIndex == 1) return(removeFirst());
  471.     else 
  472.     {    Object* max;
  473.         if (endIndex == 2)
  474.         {
  475.             max = contents[1];
  476.             contents[1] = contents[--endIndex];
  477.             trickleDownMax(1);
  478.         }
  479.         else    // endIndex >= 3
  480.         {
  481.             if (contents[1]->compare(*contents[2]) > 0)
  482.             {
  483.                 max = contents[1];
  484.                 contents[1] = contents[--endIndex];
  485.                 trickleDownMax(1);
  486.             }
  487.             else
  488.             {    
  489.                 max = contents[2];
  490.                 contents[2] = contents[--endIndex];
  491.                 trickleDownMax(2);
  492.             }
  493.         }
  494.         return(max);
  495.     }
  496. }
  497.  
  498. void Heap::reSize(int newSize)
  499. {
  500.     if (newSize > size())    contents.reSize(newSize);
  501. }
  502.  
  503. unsigned Heap::size() const    { return endIndex; }
  504.  
  505. OrderedCltn Heap::sort()
  506. //Returns heap as OrderedCltn, sorted min to max.
  507. {
  508.     Heap heap = *this;
  509.     OrderedCltn cltn(size());
  510.     for (register unsigned n=size(); n > 0; n--)
  511.         cltn.add(*heap.removeFirst());
  512.     return cltn;
  513. }
  514.  
  515. void Heap::replaceFrom(int /* start */, int /* stop */, const SeqCltn&  /* replacement */, int /* startAt */)
  516. {
  517.     shouldNotImplement("replaceFrom");
  518. }
  519.